package primary.code10_BigData;

/**
 * 大数据相关题目
 * 方法总结：
 * 1 哈希分流（拆分）
 * 2 布隆过滤器 （允许失误率）
 * 3 一致性哈希（负载）
 * 4 并查集解决岛问题（并行处理）
 * 5 位图（特殊的分段统计数量，只能表示出没出现；可以用多个位图，或多比特位图来扩展可表示的信息）
 * 6 分段统计数量（数组大小为2的幂次）
 * 7 二维堆结构（HASH分片后形成多个堆，从多个堆汇总到总堆）
 */
public class Code01_BigData {
    /*
     * 1 40亿个数字，1GB内存，查找所有未出现的数字
     * 解法：采用位图，数字的大小作为内存地址偏移量，40*10^8/8 (byte)= 500MB。
     *
     * 2 40亿个int无符号数字，4KB内存，找到一个未出现的数字
     * 解法：int类型4字节，申请数组 int[1000]，对40亿个数字进行分段统计；
     * 例如：int[0] 存储 0 ~ 2^(32-1)/1000 范围的数字出现次数；
     * 遍历int数组，对于统计值小于 2^(32-1)/1000 的范围，必定存在未出现的数字；
     * 递归上述操作，对该范围的数字进行分段统计；
     * 不断递归至存在0值，则该范围的数组没有出现
     * NOTE: 利用词频统计缩小范围
     *
     * 3 40亿个数字，有限几个变量，找到一个未出现的数字
     * 解法：同2；
     *
     * 4 100亿个URL，找到所有重复的URL
     * 解法：允许一定的失误率，布隆过滤器
     * 解法：哈希分流，使相同的url被划分到同一个小文件
     *
     * 5 100亿个数字，找到重复出现2次的数字
     * 解法：哈希分流为多个小文件，由于哈希算法的特点，相同的数字据有相同的哈希值，将被划分到同一文件中。
     *
     * 6 100亿个数字，找到中位数
     * 解法：对100亿个数字进行分段统计，根据统计的数量确定中位数所在的范围；
     * 递归对中位数所在范围的数字进行统计
     * 直到统计数量可以被内存直接运算
     *
     * 7 10G文件的数组，排序后输出
     * 解法：根据内存分配一个大根堆内存（节点数据：数值，数量）；
     * 遍历大于下限的数字，若大根堆未满或小于根节点，添加至大根堆；遍历结束后，输出大根堆，然后更新下限；
     * 递归上述操作
     *
     * 8 搜索公司每天的搜索URL次数是海量的，请计算出搜索频次TOP100的URL
     * 解法：将URL做HASH运算，分片到多个文件中，相同的URL将会被分配到相同的文件中
     * 将每个文件中的数据组织成堆结构，每个文件都弹出一个URL到总堆
     * 总堆弹出一个URL，然后从对应的文件中弹出一个URL补充到总堆
     *
     * 9 大量无符号整数中，找出所有出现恰好2次的整数
     * 解法1: hash分片处理
     * 解法2: 扩展的位图
     *
     * 10 大量无符号整数中，找到中位树
     * 解法：分段整数频次统计，缩小范围后，继续分段整数频次统计
     *
     * 11 大量的有符号整数文件，输出排序后的文件
     * 解法1: 分段词频统计
     * 解法2: 大根堆，每次输出目前为止最小的一批数
     *
     * */
}
